/*
 * fibonacci.c - Fibonacci Numbers
 */

#include <math.h>
#include "golden.h"

/*
 * F(0) = 1
 * F(1) = 1
 * F(n) = F(n-1) + F(n-2)
 */

long
fibo_rec(long n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n > 1)
		return fibo_rec(n - 1) + fibo_rec(n - 2);
}

long
fibo_ite(long n)
{
	int f[n + 1];
	int i;
	f[0] = 0;
	f[1] = 1;
	for (i = 2; i <= n; i++)
		f[i] = f[i - 1] + f[i - 2];
	return f[n];
}

/*
 *         n         n
 *        φ - (1 - φ)
 * F(n) = ------------
 *             √5
 */
double
fibo_binet(double n)
{
	return (pow(PHI, n) - pow((1 - PHI), n)) / SQRT5;
}
